GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Pattern Matching</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Pattern Matching</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p><b>Pattern Matching</b> (englisch für <i>Musterabgleich</i>) oder <b>musterbasierte Suche</b> ist ein Begriff für symbolverarbeitende Verfahren, die anhand eines vorgegebenen Musters <a href="Diskretheit" class="mw-redirect" title="Diskretheit">diskrete</a> Strukturen oder Teilmengen einer diskreten Struktur identifizieren.

</p><p>Das Pattern Matching ist beispielsweise eine Methode der phylogenetischen Analyse in der <a href="Bioinformatik" title="Bioinformatik">Bioinformatik</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Grundlagen">Grundlagen</h2></div>

<p>Eine diskrete Struktur besteht aus diskreten Elementen (<a href="Symbol" title="Symbol">Symbolen</a>) und Beziehungen zwischen diesen. Beispiele sind <a href="Zeichenkette" title="Zeichenkette">Zeichenketten</a>, aber auch <a href="Baum_(Graphentheorie)" title="Baum (Graphentheorie)">Bäume</a> oder <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graphen</a>. Das Suchmuster selbst ist ebenfalls eine diskrete Struktur, die aber durch Verwendung zusätzlicher <a href="Metazeichen" title="Metazeichen">Metazeichen</a> eine ganze Klasse von Strukturen beschreiben kann. Im Gegensatz zur <a href="Mustererkennung" title="Mustererkennung">Mustererkennung</a>, die kontinuierliche Strukturen interpretiert, operiert das Pattern Matching von vornherein auf einer symbolischen Repräsentation.

</p><p>Das Pattern Matching spielt jedoch nicht nur bei der Suche, sondern auch bei der muster- und regelbasierten Transformation diskreter Strukturen eine zentrale Rolle. In <a href="Termersetzungssystem" title="Termersetzungssystem">Ersetzungs- oder Transformationssystemen</a> bildet das Pattern Matching den ersten Schritt. Dabei werden Teile des Musters mit Teilen der analysierten Struktur identifiziert. Die gefundenen Teil-Strukturen gehen dann als Parameter in die Transformationsfunktion ein. Beispiele für solche Transformationen sind Textersetzung in Zeichenketten und <a href="Graphersetzungssysteme" class="mw-redirect" title="Graphersetzungssysteme">Graphersetzungssysteme</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Anwendungsgebiete">Anwendungsgebiete</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Programmierung">Programmierung</h3></div>

<p>In einigen <a href="Funktionale_Programmierung" title="Funktionale Programmierung">funktionalen</a> oder <a href="Logische_Programmierung" title="Logische Programmierung">logischen</a> Programmiersprachen wird Pattern Matching genutzt, um Daten anhand ihrer Struktur zu verarbeiten (z. B.: <a href="Scala_(Programmiersprache)" title="Scala (Programmiersprache)">Scala</a>, <a href="Objective_CAML" class="mw-redirect" title="Objective CAML">Objective CAML</a>, <a href="ML_(Programmiersprache)" title="ML (Programmiersprache)">ML</a>, <a href="Haskell_(Programmiersprache)" title="Haskell (Programmiersprache)">Haskell</a>, <a href="Erlang_(Programmiersprache)" title="Erlang (Programmiersprache)">Erlang</a>, <a href="Opal_(Programmiersprache)" title="Opal (Programmiersprache)">Opal</a>, <a href="Python_(Programmiersprache)" title="Python (Programmiersprache)">Python</a>).

</p><p><i>Beispiel</i> Fallunterscheidung: Eine mögliche Definition der n-ten Fibonaccizahl ist:

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{fib}}(n)={\begin{cases}0&{\text{wenn }}n=0\\1&{\text{wenn }}n=1\\{\text{fib}}(n-1)+{\text{fib}}(n-2)&{\text{sonst}}\end{cases}}}">

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</mtd>

<mtd>

<mtext>sonst</mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{fib}}(n)={\begin{cases}0&{\text{wenn }}n=0\\1&{\text{wenn }}n=1\\{\text{fib}}(n-1)+{\text{fib}}(n-2)&{\text{sonst}}\end{cases}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cc651aa045c11ae01e34508d22de84c150d6e18e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.671ex; width:48.182ex; height:8.509ex;" alt="{\displaystyle {\text{fib}}(n)={\begin{cases}0&{\text{wenn }}n=0\\1&{\text{wenn }}n=1\\{\text{fib}}(n-1)+{\text{fib}}(n-2)&{\text{sonst}}\end{cases}}}" loading="lazy"></span>

</p><p>Diese Definition kann so mithilfe von Pattern Matching direkt nach <a href="Haskell_(Programmiersprache)" title="Haskell (Programmiersprache)">Haskell</a> übertragen werden.

</p>

<div class="mw-highlight mw-highlight-lang-haskell mw-content-ltr" dir="ltr"><pre><span></span><span class="c1">-- Matcht die ersten beiden Fälle</span>

<span class="c1">-- Alle anderen Zahlen n sind definiert als</span>

</pre></div>

<p><i>Beispiel:</i> In Haskell werden die Argumente in einer Funktionsdefinition mit Pattern gematcht. Ein Pattern kann, muss aber nicht, wie im vorherigen Beispiel, ein elementarer Wert (zum Beispiel 0) sein, sondern kann auch einen Daten-Konstruktor beschreiben.

</p>

<div class="mw-highlight mw-highlight-lang-haskell mw-content-ltr" dir="ltr"><pre><span></span><span class="c1">-- matcht die leere Liste (Konstruktor [])</span>

<span class="c1">-- matcht alle Listen der Länge > 0 (Konstruktor :), wobei x den Kopf und xs den Listenrest enthält</span>

</pre></div>

<p>Das äquivalente Beispiel in der Syntax von Python (ab Version 3.10):<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-highlight mw-highlight-lang-haskell mw-content-ltr" dir="ltr"><pre><span></span><span class="nf">match</span><span class="w"> </span><span class="n">n</span><span class="kt">:</span>

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="Textverarbeitung">Textverarbeitung</h3></div>

<div class="hauptartikel" role="navigation"><span class="hauptartikel-pfeil" title="siehe" aria-hidden="true" role="presentation">→ </span><i><span class="hauptartikel-text">Hauptartikel</span>: <a href="String-Matching-Algorithmus" title="String-Matching-Algorithmus">String-Matching-Algorithmus</a></i></div>

<p>Pattern Matching wird auch verwendet, um Text zu bearbeiten. In Programmiersprachen wie <a href="Perl_(Programmiersprache)" title="Perl (Programmiersprache)">Perl</a> oder <a href="Awk" title="Awk">awk</a> und auch in den meisten <a href="Texteditor" title="Texteditor">Texteditoren</a> existieren Werkzeuge, um einen Text nach einem Muster zu durchsuchen. Die Muster bestehen aus <a href="Regul%C3%A4rer_Ausdruck" title="Regulärer Ausdruck">regulären Ausdrücken</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li><a href="Suchverfahren" title="Suchverfahren">Suchverfahren</a></li>

<li><a href="Musteranalyse" title="Musteranalyse">Musteranalyse</a></li>

<li><a href="Levenshtein-Distanz" title="Levenshtein-Distanz">Levenshtein-Distanz</a></li>

<li><a href="Gestalt_Pattern_Matching" title="Gestalt Pattern Matching">Gestalt Pattern Matching</a></li>

<li><a href="Unscharfe_Suche" title="Unscharfe Suche">Unscharfe Suche</a></li>

<li><a href="Phonetische_Suche" title="Phonetische Suche">Phonetische Suche</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li><a href="Simon_Peyton_Jones" title="Simon Peyton Jones">Simon Peyton Jones</a> (Hrsg.): <cite class="lang" lang="en" dir="auto" style="font-style:italic">Haskell 98 Language and Libraries: The Revised Report</cite>. Cambridge University Press, 2003, ISBN 0-521-82614-4 (englisch, <a rel="nofollow" class="external text" href="http://www.haskell.org/onlinereport/">haskell.org</a> – Abschnitt 3.17, <a rel="nofollow" class="external text" href="https://www.haskell.org/onlinereport/exps.html#pattern-matching">HTML-Version</a>).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Pattern+Matching&rft.btitle=Haskell+98+Language+and+Libraries%3A+The+Revised+Report&rft.date=2003&rft.genre=book&rft.isbn=0521826144&rft.pub=Cambridge+University+Press" style="display:none"> </span></li>

<li>Richard Bird: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Introduction to Functional Programming using Haskell</cite>. 2. Auflage. Prentice Hall Europe, 1998, ISBN 0-13-484346-0 (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Pattern+Matching&rft.au=Richard+Bird&rft.btitle=Introduction+to+Functional+Programming+using+Haskell&rft.date=1998&rft.edition=2.&rft.genre=book&rft.isbn=0134843460&rft.pub=Prentice+Hall+Europe" style="display:none"> </span></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text"><span class="cite">Daniel F. Moisset: <a rel="nofollow" class="external text" href="https://peps.python.org/pep-0636/"><i>PEP 636 – Structural Pattern Matching: Tutorial.</i></a> In: <i>python.org.</i> 12. September 2020,<span class="Abrufdatum"> abgerufen am 28. Juni 2022</span> (englisch).</span><span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3APattern+Matching&rft.title=PEP+636+%E2%80%93+Structural+Pattern+Matching%3A+Tutorial&rft.description=PEP+636+%E2%80%93+Structural+Pattern+Matching%3A+Tutorial&rft.identifier=https%3A%2F%2Fpeps.python.org%2Fpep-0636%2F&rft.creator=Daniel+F.+Moisset&rft.date=2020-09-12&rft.language=en"> </span></span>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2022-06-28" href="https://de.wikipedia.org/wiki/?title=Pattern_Matching&oldid=224062922">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>